package demo7;

import java.util.Arrays;

/**
 * 数组的归并排序
 */
public class Main3 {
    public static void main(String[] args) {
        int[] arr = {5,2,8,6,1,9,10,45,12};
        System.out.println(Arrays.toString(arr));
        //mergeSort(arr,0,arr.length-1);
        //quickSort(arr,0,arr.length-1);
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr,int left,int right){
        if(left >= right) return;
        int mid = left + (right-left)/2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,mid,right);  // 始终操作的是原数组
    }


    // 把数组中的left -> mid段 和 mid+1 -> right段合并
    public static void merge(int[] arr,int left,int mid,int right){
        // 建一个辅助数组
        int[] newArr = new int[right-left+1];
        int index= 0;
        int p1 = left;
        int p2 = mid+1;
        while(p1 <= mid && p2 <= right){
            if(arr[p1] <= arr[p2]){
                newArr[index] = arr[p1];
                p1++;
            }else{
                newArr[index] = arr[p2];
                p2++;
            }
            index++;
        }
        //如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p1<=mid){
            newArr[index++] = arr[p1++];
        }
        //如果第二个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p2<=right){
            newArr[index++] = arr[p2++];
        }

        // 复制回原素组 的left 到right
        for (int i = 0; i < right-left+1; i++) {
            arr[left + i] = newArr[i];
        }
    }

    // 快速排序
    public static void quickSort(int[] arr, int start, int end){
        if(start >= end) return;;

        int temp = arr[start];
        int left = start;
        int right = end;

        while(left < right){
            while(left < right && temp < arr[right]){
                right--;
            }
            arr[left] = arr[right];

            while(left < right && temp > arr[left]){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;

        quickSort(arr,start,left);
        quickSort(arr,left+1,right);

    }


    // 冒泡排序
    public static void bubbleSort(int[] arr){
        int len = arr.length;

        for (int i = 0; i < len-1; i++) {  // 控制共比较多少轮 len-1轮
            for (int j = 0; j < len-1-i; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

    }





}
